1. Field of the Invention
The present invention relates, in general, to software, systems and methods for dynamic priority conflict resolution in multiprocessor computer systems and more particularly to conflict resolution in multiprocessor computer systems having shared memory with equal priority values.
2. Relevant Background
Symmetric Multi-Processing (“SMP”) is defined as the connection of more than one homogeneous processor to a single, monolithic central memory. However, until recently, hardware and software limitations have minimized the total number of physical processors that could access a single memory efficiently. These limitations have reduced the ability to maintain computational efficiency as the number of processors in a computer system increased, thus reducing the overall scalability of the system. With the advent of faster and ever more inexpensive microprocessors, large processor count SMP systems are becoming available and hardware advances have allowed interconnected networks to multiplex hundreds of processors to a single memory with a minimal decrease in efficiency.
Nevertheless, in any computer system that employs multiple processors which share the same memory space, it is possible that at least two processors may try to access the same memory simultaneously. In this instance a “conflict” is said to exist. In addition to memory, conflicts may also arise for any single element in the system wherein multiple users may require substantially concurrent access. An example of this type of conflict might occur when a port on a crossbar switch is used to route incoming signals from multiple ports to a selected output port; also a situation requiring conflict resolution. To resolve such conflicts, special circuitry must be added to the computer system in order to determine which device is allowed to access memory or another system resource at any given time.
The simplest of these circuits merely assigns a predetermined priority value to each of the processors in the system. when a conflict occurs, the circuit grants access to the highest priority processor. Any other processor must try to access memory at a later time, which causes it to be delayed. Although this circuit is easy to implement, it has several major drawbacks. First, it is possible for a single, high-priority processor to continually access the resource and prevent lower priority processors from ever getting access to it. This event will stall out the other processors and greatly reduce system performance. Secondly, as the number of processors increase, so will the likelihood of an unfair access event happening. As a result, it has been very difficult to build shared memory computers with hundreds of processors and still have the performance of that system scale well beyond 64 processors.
One solution to resolving conflicts between multiple processors attempting to access the same memory is disclosed in U.S. Pat. No. 6,026,459 (“the '459 patent”), assigned to SRC Computers, Inc. of Colorado Springs, Colo. The system and method disclosed in the '459 patent advantageously overcomes this memory access priority problem and is of especial utility in affording equal priority access to the shared memory resources by all processing devices.
The functionality of the system disclosed in the '459 patent is to resolve conflicts within a crossbar switch used to connect the processors to the shared memory in a computer system. In a computer system utilizing a relatively large number of processors, it is necessary to ensure that all processors have equal priority to access memory over time. In operation, a priority level for each input port is maintained by each output port. On power up, these priority levels are predetermined in accordance with the particular computer system design. When a conflict for a particular output port occurs, the priority levels of the conflicting inputs are evaluated and access is initially granted to the highest priority input. Once this initial access is granted, the priority level of the “winning” input is then changed to the lowest priority level and the priority of all of the other inputs is increased by one.
Through use of this technique, all inputs will transition through all of the possible priority levels based upon their usage of the output and an input that has just been given access to the output will have a low priority, whereas an input that has not recently accessed the output will have a higher priority. Inasmuch as only those inputs that require access to the output are evaluated, the system as disclosed in the '459 patent always allows a useful connection. In addition, the input that has least recently used the output will be allowed access to it.
But since it is possible that an input may not need access to a particular output port for some time, its priority will over time be incremented to the highest level, where it will remain. This incremental advancement to the highest priority level may occur for more than one port as the highest level priority is the only priority level that can legitimately be held by more than one input at a time. As a consequence, a mechanism is needed to deal with a conflict between inputs that all have the highest priority level. This priority level tie might also be encountered in the event of a circuit error that inappropriately assigned the same priority to two differing inputs.
One solution disclosed in U.S. Pat. No. 6,026,459 to resolve ties of this natures is to default back to the original predetermined priorities when a priority conflict occurs. This action breaks the tie and allows the circuit to continue to function but may create unfair access patterns when many similar ties occur over time. While this approach guarantees that no input will be blocked indefinitely and that the longest wait for any input will be equal to the time duration for which access is granted, multiplied by the total number of inputs it results in the same winner being chosen if repeated ties occur. What is needed are methods and systems that can fairly resolve conflicts between inputs that simultaneously possess the highest priority level.
A second fairness concern in implementation of techniques such as the one disclosed in the '459 patent is a recurring processor selection phenomena with respect to semaphore access. In multitasking systems, a semaphore is a variable with a value that indicates the status of a common resource. It's used to lock the resource that is being used. A process needing the resource checks the semaphore to determine the resource's status and then decides how to proceed. If a processor seeking a particular semaphore finds it locked it must wait until the semaphore once again becomes available. Current system provide unfair access to such semaphores. In a typically scenario two or more processors will simultaneously seek access to the same semaphore. Based on schemes such as described in the '459 patent a conflict in access to the semaphore will be resolved by a priority comparison. Such a priority comparison will result in a reoccurring pattern of selection that is skewed. What is needed are method and systems that can fairly resolve conflicts between inputs seeking access to a semaphore.